#define _CRT_SECURE_NO_WARNINGS 1

//二叉树的层序遍历
//写法一：
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        vector<vector<int>> ret;
        if (root == nullptr)
        {
            return ret;
        }

        queue<TreeNode*> q;
        vector<int> v;
        q.push(root);

        int level = q.size();
        while (!q.empty())
        {
            v.push_back(q.front()->val);

            if (q.front()->left)
            {
                q.push(q.front()->left);
            }
            if (q.front()->right)
            {
                q.push(q.front()->right);
            }

            q.pop();
            level--;
            if (level == 0)
            {
                level = q.size();
                ret.push_back(v);
                v.clear();
            }
        }

        return ret;
    }
};
//写法二：
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        int levelSize = 0;
        if (root)
        {
            q.push(root);
            levelSize = q.size();
        }
        while (!q.empty())
        {
            vector<int> v;
            while (levelSize--)
            {
                TreeNode* front = q.front();
                v.push_back(front->val);
                q.pop();

                if (front->left)
                {
                    q.push(front->left);
                }
                if (front->right)
                {
                    q.push(front->right);
                }
            }
            vv.push_back(v);
            levelSize = q.size();
        }
        return vv;
    }
};